The invention relates generally to electronic commerce and transactions. More particularly, the invention relates to techniques for enabling users to engage in fair or simultaneous electronic transactions using a semi-trusted third party, and in the case of fraudulent behavior by a user, prevent the disclosure of any electronic information until the exchange, and authentication of information is complete.
Recently there has been a proliferation of information networks such as computer, telephone, cable, energy and others. The presence of these networks has tremendously improved the efficiency and convenience of many transactions (i.e., exchanges) while lowering associated costs. Yet more recently, digital signatures and public-key encryption have added much needed security to these electronic transactions. This functionality makes electronic communication channels articularly suitable for financial transactions, i.e., electronic commerce.
A problem endemic to electronic transactions is the need for simultaneity. The term "simultaneity" as used herein means an electronic transaction that is structured to guarantee certain actions will take place if and only if certain other actions take place. In the case of payment protocols, simultaneity can ensure that a customer receives a document from a vendor if and only if the vendor receives payment from the customer. Similarly, simultaneity can ensure that a certified electronic mail is delivered to its destination if and only if proof of that delivery is given to its sender.
The absence of simultaneity in electronic transactions severely limits electronic commerce. This can be illustrated using certified electronic mail as an example. A certified mail transaction typically includes a sender, e.g., Tracey, who wishes to deliver a given message to an intended recipient, e.g., Alex. Tracey could try to get a receipt from Alex of an electronic message m by sending m to Alex in clear text form, i.e., unencrypted. If message m was something as important as Tracey's electronic signature for an electronic payment, a dishonest Alex might be motivated to discontinue the conversation once he receives m. Alex could therefore deprive Tracey of any proof of delivery. Conversely, Alex may find unacceptable the idea of sending a blank receipt to Tracey prior to receiving m.
The simultaneity problem does not disappear by simply adding a few more rounds of communication. For example, it is possible for Tracey to send Alex an encryption of m, for which Alex would return his digital signature of this ciphertext as an "intermediate" receipt. Tracey would then send him the decryption key, for which Alex would send a final receipt.
This transaction does not guarantee simultaneity as well. It simply adds one more layer of complexity which merely delays the point where Alex may engage in dishonest behavior. Alex may refuse to send Tracey any receipt after receiving Tracey's decryption key. Alex's signature of the encrypted message would not constitute a valid receipt since there is no proof that Tracey sent Alex her key.
Various cryptographic approaches exist in the literature that attempt to solve similar problems, but they are not satisfactory in many respects. Some of these methods applicable to multi-party scenarios propose use of verifiable secret sharing, or multi-party protocols for making simultaneous some specific transactions between parties. These methods, however, require a plurality of parties. Furthermore, a majority of these party members must be honest. This greatly increases the complexity of the transaction. Furthermore, these methods require several rounds of transmission, which greatly increases overhead. Thus, these techniques are generally impractical. Moreover, these techniques are incapable of ensuring simultaneity for two party transactions.
Sophisticated cryptographic transactions between two parties have been developed. These cryptographic transactions, however, do not guarantee simultaneity. As illustrated with our certified electronic mail example, these techniques merely delay the point at which dishonest behavior can occur.
There have been several specific attempts made at providing simultaneity for two-party transactions. These attempts, however, use assumptions or methods that are unsatisfactory in various ways. For example, an article by M. Blum titled "How to exchange (secret) keys," ACM Transactions on Computer Systems, vol. 1, No. 2, May 1983, pp. 175-193, describes transactions that include contract signing and certified mail. These techniques, however, are very complex and require a large number of rounds of communication.
The method of Luby et al. given in a paper titled "How to simultaneously exchange a secret bit by flipping a symmetrically-biased coin," 1983, allows two parties to exchange the decryption of two given ciphertexts in a special way. Both parties leak information to each other such that the probability that one party will guess correctly the clear text of the other is slowly increased towards 100%. This method, however, does not guarantee simultaneity since one party could quit the protocol with a slight advantage.
The most recent attempts for achieving simultaneity for two party transactions involve the use of one or more external entities. These external entities are often referred to as "centers", "servers" or "trustees." Examples of the use of external entities to achieve fair exchange is outlined in a paper by S. Ketchpal titled "Transaction protection for information buyers and sellers," Proceedings of the Dartmouth Institute for Advanced Graduate Studies '95, 1995. These external entities are referred to as "fully-trusted" third parties since they are assumed to be honest. The techniques using fully-trusted third parties, however, quickly break down in the presence of dishonest behavior in the case of human third parties, or equipment malfunction or tampering in the case of electronic third parties. Moreover, these techniques are incapable of determining whether the third party is operating in the proper manner.